package com.example.demo.module.calculate;

import lombok.Data;

import java.util.List;
import java.util.Stack;

/**
 * @author lufei
 * @version 1.0
 * @created 18-6-15
 */
@Data
public class BinaryTree {

    public static void main(String[] args) {

    }

    @Data
    class Node {
        int var;
        Node left;
        Node right;

        public Node(int var) {
            this.var = var;
            this.left = null;
            this.right = null;
        }
    }

    private void createBinaryTree(int[] datas, List<Node> nodeList) {
        //将数组变成node节点
        for (int nodeindex = 0; nodeindex < datas.length; nodeindex++) {
            Node node = new Node(datas[nodeindex]);
            nodeList.add(node);
        }
        //给所有富姐点设定子节点
        for (int index = 0; index < nodeList.size() / 2 - 2; index++) {
            nodeList.get(index).setLeft(nodeList.get(index * 2));
            nodeList.get(index).setRight(nodeList.get(index * 2 + 1));
        }
        //单独处理最后一个父亲节点，因为有可能没有又接点
        int index = nodeList.size() / 2 - 1;
        nodeList.get(index).setLeft(nodeList.get(index * 2 + 1));
        if (nodeList.size() % 2 == 1) {
            nodeList.get(index).setRight(nodeList.get(index * 2 + 2));
        }
    }

    /**
     * 递归前序遍历
     * @param root
     */
    public void preOrderTraversal(Node root) {
        if (root == null) {
            return;
        }
        System.out.println(root.var);
        preOrderTraversal(root.left);
        preOrderTraversal(root.right);
    }

    /**
     * 递归中需遍历
     * @param root
     */
    public void inOrderTraversal(Node root) {
        if (root == null) {
            return;
        }
        inOrderTraversal(root.getLeft());
        System.out.println(root.var);
        inOrderTraversal(root.getRight());
    }

    /**
     * 递归后续遍历
     * @param root
     */
    public void postOrderTraversal(Node root) {
        if (root == null) {
            return;
        }
        postOrderTraversal(root.left);
        postOrderTraversal(root.right);
        System.out.println(root.var);
    }

    /**
     * 非递归的前序遍历
     * @param root
     */
    public void preOrderTraversalbyLoop(Node root) {
        Stack<Node> stack = new Stack<>();
        Node p = root;
        while (p != null || !stack.isEmpty()) {
            while (p != null) {
                System.out.println(p.var);
                stack.push(p);
                p = p.getLeft();
            }
            if (!stack.isEmpty()) {
                p = stack.pop();
                p = p.getRight();
            }
        }
    }




}
